/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


/**
 * 核心思想
 * https://leetcode-cn.com/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode/
 */

// 按行排序
// class Solution {
// public:
//     string convert(string s, int numRows) {
//         if (numRows == 1) return s;
//         vector<string> rows(min(numRows, int(s.size())));
//         int curRow = 0;
//         bool goingDown = false;

//         for (char c : s) {
//             rows[curRow] += c;
//             if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
//             curRow += goingDown ? 1 : -1;
//         }

//         string ret;
//         for (string row : rows) ret += row;
//         return ret;
//     }
// };


// 按行访问
class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1) return s;

        string ret;
        int n = s.size();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret += s[j + i];
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret += s[j + cycleLen - i];
            }
        }
        return ret;
    }
};



int main(int argc, const char** argv) {
    Solution solu = Solution();
    string s = "PAYPALISHIRING";
    int numRows = 4;
    cout << s.size() << endl;
    cout << solu.convert(s, numRows) << endl;

    return 0;
}